/// @tags: NetworkFlow
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define id(i, j) (((i)-1) * n + (j))

using namespace std;

namespace BlueQuantum {

constexpr int MAXN = 2e2 + 3, INF = 0x3f3f3f3f;
constexpr int dx[] = {1, 1, 2, 2, -1, -1, -2, -2}, dy[] = {-2, 2, -1, 1, -2, 2, -1, 1};

int ecnt = 1;
int heads[MAXN * MAXN], cur[MAXN * MAXN], dep[MAXN * MAXN];
bool ban[MAXN][MAXN];

struct Edge {
  int v, nxt, f;
} e[MAXN * MAXN * 16];

inline void add(int u, int v, int f) {
  e[++ecnt].v = v, e[ecnt].nxt = heads[u], heads[u] = ecnt, e[ecnt].f = f;
  e[++ecnt].v = u, e[ecnt].nxt = heads[v], heads[v] = ecnt, e[ecnt].f = 0;
}

inline bool bfs(int s, int t) {
  memset(dep, 0, sizeof(dep));
  memcpy(cur, heads, sizeof(cur));
  queue<int> q;
  q.push(s);
  dep[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = heads[u], v; i; i = e[i].nxt) {
      if (dep[v = e[i].v] == 0 && e[i].f) {
        dep[v] = dep[u] + 1;
        if (v == t) return true;
        q.push(v);
      }
    }
  }
  return false;
}

int dinic(int u, int t, int flow) {
  if (u == t) return flow;
  int rest = flow, k;
  for (int &i = cur[u], v; i; i = e[i].nxt) {
    if (dep[v = e[i].v] == dep[u] + 1 && e[i].f) {
      k = dinic(v, t, min(flow, e[i].f));
      e[i].f -= k, e[i ^ 1].f += k;
      rest -= k;
      if (rest == 0) break;
    }
  }
  return flow - rest;
}

inline int getMaxFlow(int s, int t) {
  int res = 0;
  while (bfs(s, t)) res += dinic(s, t, INF);
  cerr << res << endl;
  return res;
}

inline int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1, x, y; i <= m; ++i) {
    cin >> x >> y;
    ban[x][y] = true;
  }
  int s = 0, t = n * n + 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (!ban[i][j]) {
        ((i + j) & 1) ? add(s, id(i, j), 1) : add(id(i, j), t, 1);
        if (((i + j) & 1))
          for (int k = 0; k < 8; ++k) {
            int tx = i + dx[k], ty = j + dy[k];
            if (tx >= 1 && ty >= 1 && tx <= n && ty <= n)
              if (!ban[tx][ty]) add(id(i, j), id(tx, ty), INF);
          }
      }
    }
  }
  cout << n * n - m - getMaxFlow(s, t);
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P3355 骑士共存问题.in", "r", stdin);
  freopen("P3355 骑士共存问题.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
